#Class file for SudokuPuzzle

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

Node = Struct.new(:top, :bottom, :left, :right, :colHeader, :row, :column, :value, :header) do
          def initialize(x=nil, y=nil, z=nil)
               self.row = y
               self.column = x
               self.value = z
               self.header = false
          end
     end

MATRIX_SIZE = 9
MAX_ROWS = MATRIX_SIZE ** 3
MAX_COLS = MATRIX_SIZE ** 2 * 4
ROW_OFFSET = 0
COL_OFFSET = MATRIX_SIZE ** 2
BOX_OFFSET = 3 * COL_OFFSET
CELL_OFFSET = 2 * COL_OFFSET
ROW_BOX_DIVISOR = 3
COL_BOX_DIVISOR = 3


class SudokuMatrix
     # a quadruply-linked circular list (Dancing Links) that uses Algorithm X to solve exact cover

     #729 columns by 324 rows
     #this stems from 81*4 constraints = 324 columns
     #and 9*9*9 possibilities = 729 rows
     #the constraints are 1) Every row must have values 1-9, and there are 9 rows = 81 constraints
     #					  2) Every column must have values 1-9, and there are 9 columns = 81 constraints
     #					  3) Every box must have values 1-9, and there are 9 boxes = 81 constraints
     #					  4) Every cell must have a value, and there are 9*9 cells = 81 constraints
     #Clearly, satisfying one constraint could satisfy another (if we place 1 at 1,1 then we've satisfied the constraints 
     #that row 1 must have value 1 in it, column 1 must have value 1 in it, box 1 must have value in it, and cell 1,1 must 
     #have a value in it. One entry into the puzzle solution satisfies 4 constraints
     #There are 729 rows because there are 729 subsets of size 4 {r,c,b,v} the box value is determined by r and c, so it is 
     #disregarded.
     # row1column1value1, row1column1value2,...,row1column1value9,...,row9column9value9 = 9*9*9 = 729 combinations

     
     #The matrix representation I'm using is as follows:
     #          RV					ColV				RCFilled 				BV
     #RCV		--					----				--------				--
     #          11 12 13 14 ... 99  11 12 13 14 ... 99  11 12 13 14 ... 99		11 12 13 14 ... 99	
     #---------------------------------------------------------------------------------------------
     #111      1 0  0  0      0    1  0  0  0      0   1  0  0  0      0       1  0  0  0      0
     #112      0 1  0  0      0    0  1  0  0      0   1  0  0  0      0       0  1  0  0      0
     #113
     #114
     #.
     #.
     #.
     #119
     #121
     #122
     #.
     #.
     #.
     #999


     #Where RV is Row-Value pairs, ColV = Column-Value pairs, RCFilled is Cell-Filled pairs (is there a value in the cell?),
     #and BV is Box-Value pairs the matrix is a boolean matrix of 1s and 0s, 1 if RV and RC intersect and 0 elsewise

     #(note, I will be using 0-8 instead of 1-9. A printout of the complete above matrix can be found in exactCover.txt, 
     #though I have not included row and column headings)
     
     #A sudoku grid will have its boxes labelled in row-dominant order (left right ordering before up and down).
     #Therefore a 9X9 grid has boxes: 0 1 2
     #                                        3 4 5
     #                                        6 7 8
     
     @root     #points to a placeholder node that doesn't correspond to anything meaningful, but acts 
               #as an anchor from which to explore the matrix.
     @workingSolution = []#contains the partial or full solution to the current puzzle
     @puzzleNodes = []
     @solved = false #if solution has been found true, else false.
     @count = 0
     
     def SudokuMatrix.isWellFormed(a) 
     #checks an array to see if it represents a well-formed sudoku input. Returns true/false
     #can only contain numbers 0-9 and must be 81 characters long. This does not determine whether or
     #not the puzzle is solvable. Cannot contain string versions of numbers '0'..'9'
         puts "isWellFormed"
         result = true
         a.select! { |x| (0..MATRIX_SIZE).member?(x) }
         result = false unless a.length == MATRIX_SIZE ** 2
         result
     end
     
     def initialize() 
     puts "initialize"
     #creates the blank sudoku puzzle structure
     #this is the set of all possible choices for each spot as a row and the columns being which constraints
     #that row would satisfy
          #first create a root linked to itself
          @root = Node.new()
          @root[:header] = true
          @root[:column] = "root"
          @root[:right] = @root
          @root[:left] = @root
          @root[:top] = @root
          @root[:bottom] = @root
          
          matrix = Array.new(MAX_ROWS) {Array.new(MAX_COLS)}
          (0...MATRIX_SIZE).each do |x| 
               (0...MATRIX_SIZE).each do |y| 
                    (0...MATRIX_SIZE).each do |z| 
                         #find which row this refers to (x is the column, y is the row and z is the value in the square)
                         row = (x*COL_OFFSET)+(y*MATRIX_SIZE)+z 
                         rowNode = Node.new(x, y, z)
                         matrix[row][0+(y*MATRIX_SIZE)+z] = rowNode
                         #This finds the column in the "row section" of the columns that this row satisfies
                         colNode = Node.new(x,y,z)
                         matrix[row][COL_OFFSET+(x*MATRIX_SIZE+z)] = colNode
                         #This finds the column in the "columns section" of the columns that this row satisfies
                         cellNode = Node.new(x,y,z)
                         matrix[row][CELL_OFFSET+(y*MATRIX_SIZE+x)] = cellNode
                         #This finds the column in the "Whether a value is present in that square" section of the columns that this 
                         #row satisfies
                         boxNode = Node.new(x,y,z)
                         matrix[row][BOX_OFFSET+((x/ROW_BOX_DIVISOR + y/COL_BOX_DIVISOR * COL_BOX_DIVISOR) * MATRIX_SIZE + z)] = boxNode
                         
                         #This finds the column in the "box section" of the columns that this row satisfies
                         #the weird math is because the matrix is set up to consider the boxes from left to right and top to bottom
                         
                         #now we link the boxes
                         rowNode[:right] = colNode
                         rowNode[:left] = boxNode
                         colNode[:right] = cellNode
                         colNode[:left] = rowNode
                         cellNode[:right] = boxNode
                         cellNode[:left] = colNode
                         boxNode[:right] = rowNode
                         boxNode[:left] = cellNode
                    end
               end
          end
          #Now we need to link the columns together.
          
          (0...MAX_COLS).each do |j|
               #link the header to itself
               nextColHeader = Node.new
               nextColHeader[:header] = true
               nextColHeader[:column] = j
               nextColHeader[:top] = nextColHeader
               nextColHeader[:bottom] = nextColHeader
               nextColHeader[:left] = nextColHeader
               nextColHeader[:right] = nextColHeader
               nextColHeader[:colHeader] = nextColHeader
               nextColRow = nextColHeader
               counter = 0
               #go through each node in the matrix in that column and link it from top bottom and to header
               (0...MAX_ROWS).each do |i|
                    if matrix[i][j] != nil
                         matrix[i][j][:top] = nextColRow
                         nextColRow[:bottom] = matrix[i][j]
                         matrix[i][j][:bottom] = nextColHeader
                         nextColHeader[:top] = matrix[i][j]
                         matrix[i][j][:colHeader] = nextColHeader
                         nextColRow = matrix[i][j]
                         counter += 1
                    end
               end
               #puts "Column " + j.to_s + " has " + counter.to_s + " nodes"
               puts "Error! Column has no rows! Column number: " + j.to_s if nextColHeader[:bottom].equal? nextColHeader
               puts "Error adding column!" unless addColumn(nextColHeader)
          end
     end
     
     def clearPuzzle() #removes loaded puzzle and resets matrix
          puts "clearPuzzle"
          until @puzzleNodes.length == 0
               node = @puzzleNodes.pop()
               colNode = node[:colHeader]
               rowNode = node[:right]
               until rowNode.equal? node
                    uncover(rowNode[:colHeader])
                    rowNode = rowNode[:right]
               end
               uncover(colNode)
          end
          
          until @workingSolution.length == 0 
               @workingSolution.pop()
          end
     end
     
     def solvePuzzle() #Takes a loaded puzzle and solves it
          return true if isEmpty()
          puts "solvePuzzle"
          
          @count = 0
          @solved = false
          nextCol = chooseNextColumn()
          
          return false if (@count < 1)
          
          nextRowInCol = nextCol[:bottom]
          cover(nextCol)
          
          puts nextRowInCol.equal? nextCol
          puts @solved
          
          until nextRowInCol.equal? nextCol or @solved
               puts "entering solve loop"
               @workingSolution.push(nextRowInCol)
               rowNode = nextRowInCol[:right]
               until rowNode.equal? nextRowInCol
                    cover (rowNode[:colHeader])
                    rowNode = rowNode[:right]
               end
               
               @solved = solvePuzzle()
               
               @workingSolution.pop() unless @solved
               
               rowNode = nextRowInCol[:right]
               until rowNode = nextRowInCol
                    uncover(rowNode[:colHeader])
                    rowNode = rowNode[:right]
               end
               
               nextRowInCol = nextRowInCol[:bottom]
          end
          puts "exited solve loop"
          
          uncover nextCol
          
          return @solved #either finished, or column couldn't be satisfied with current configuration.
     end
     
	 
	 #this is the iterative version of the above.
	 def _solvePuzzle() #Takes a loaded puzzle and solves it
        @solved = false
		
		#push first column on stack
		#continue until @solved or stack = empty
			#pop item off stack
			#check if @solved, if not
			#push all of its children on stack
			
		@solved = false
		firstCol = chooseNextColumn
		nextRowInCol = firstCol[:bottom]
		testStack = []
		until nextRowInCol.equal? firstCol
			testStack.push(nextRowInCol)
			nextRowInCol= nextRowInCol[:bottom]
		end
		
		loop do
			testNode = testStack.pop()
			cover(testNode[:colHeader])
			@workingSolution.push(testNode)
			rowNode = testNode[:right]
			
			until rowNode.equal? testNode
				cover(rowNode[:colHeader])
				rowNode = rowNode[:right]
			end
			
			if isEmpty() 
				@solved = true
				break
			end
			
			nextCol = chooseNextColumn()
			unless @count < 1
				nextRowInCol = nextCol[:bottom]
				until nextRowInCol.equal? nextCol
					testStack.push(nextRowInCol)
					nextRowInCol = nextRowInCol[:bottom]
				end
			end
			
			if @count < 1
				testNode = @workingSolution.pop()
				uncover(testNode)
				rowNode = testNode[:right]
				until rowNode.equal? testNode
					uncover(rowNode[:colHeader])
					rowNode = rowNode[:right]
				end
			end
			
			break if testStack.length == 0
		end
		
     end
	 
     def loadPuzzle(a) 
          puts "loadPuzzle"
     #requires a well-formed sudoku puzzle in a. Can be checked with isWellFormed class method
          @solved = true if a.select { |x| (1..MATRIX_SIZE).member?(x)} #this is a naive method that takes a fully filled out
                                                                       #sudoku puzzle to be complete
                                                                       #could be improved by a checking method
          @workingSolution = []
          @puzzleNodes = []
          
          for ind in 0...81
               x = a[ind]
               unless x == 0
                    i = ind % 9
                    j = ind / 9
                    nodeToFind = Node.new(i,j,x)
                    found = find(nodeToFind)
                    puts "Error in Matrix" if found == nil
                    @puzzleNodes.push(found)
                    colNode = found
                    #rowNode = found[:right]
                    deleteUnusedNodes(colNode)
                    #until rowNode == found
                    #     nextNode = rowNode[:right]
                    #     deleteUnusedNodes(rowNode[:colHeader])
                    #     rowNode = nextNode
                    #end
               end
          end
     end
     
     def printSolution()
          puts "printSolution"
          a = Array.new(81) {|x| x=0}
          @puzzleNodes.each do |x|
               a[x[:row]*MATRIX_SIZE + x[:column]] = x[:value]
          end
          puts @workingSolution.length
          @workingSolution.each do |x|
               a[x[:row]*MATRIX_SIZE + x[:column]] = x[:value]
          end
          
          for i in 0...81
               print a[i]
               print "|" if i % 3 == 2 and i % 9 != 8
               print "\n" if i % 9 == 8 
          end
     end
     
     private
     
     def addColumn(newNode) #Pass this the header of a column
          puts "addColumn"
          return false unless newNode[:header]
          r = @root
          newNode[:left] = r[:left]
          newNode[:right] = r
          r[:left][:right] = newNode
          r[:left] = newNode
          #print newNode[:left][:column].to_s + "<->" + newNode[:column].to_s + "<->" +  newNode[:right][:column].to_s
          #print "\n"
          #print r[:left][:column].to_s + "<->" + r[:column].to_s
          #print "\n"
          return true
     end
     
     def deleteUnusedNodes (r)  #requires: node
          colNode = r[:colHeader]
          colNode[:right][:left] = colNode[:left] #removes from list
          colNode[:left][:right] = colNode[:right]
          colNode[:top][:bottom] = nil
          colNode[:bottom][:top] = nil
          colNode[:colHeader] = nil
          
          rowNode = colNode[:bottom]
          until rowNode == nil
               rightNode = rowNode[:right]
               until rightNode == nil
                    currentNode = rightNode
                    rightNode = rightNode[:right]
                    currentNode[:top][:bottom] = currentNode[:bottom] unless currentNode[:top] == nil
                    currentNode[:bottom][:top] = currentNode[:top] unless currentNode[:bottom] == nil
                    currentNode[:colHeader] = nil if currentNode[:right] == nil
                    currentNode[:left][:right] = nil unless currentNode[:left] == nil
                    currentNode[:right][:left] = nil unless currentNode[:right] == nil
                    currentNode[:right] = nil
                    currentNode[:left] = nil
               end
               rowNode = rowNode[:bottom]
          end
          colNode[:top] = nil
          colNode[:bottom] = nil
          colNode[:left] = nil
          colNode[:right] = nil
          ObjectSpace.garbage_collect
     end
     
     def isEmpty()
          puts "isEmpty"
          return @root[:right].equal? @root
     end
     
     def cover(r) #this function 'hides' a chunk of the matrix to show that that constraint has been satisfied
                       #removes the column to show it has been satisfied as well as all other columns that row satisfies
                       #since each constraint may only be satisfied once.
          puts "cover"
          colNode = r[:colHeader]
          colNode[:right][:left] = colNode[:left] #removes from list
          colNode[:left][:right] = colNode[:right]
          
          rowNode = colNode[:bottom]
          until rowNode.equal? colNode
               rightNode = rowNode[:right]
               until rightNode.equal? rowNode
                    rightNode[:top][:bottom] = rightNode[:bottom]
                    rightNode[:bottom][:top] = rightNode[:top]
                    rightNode = rightNode[:right]
               end
               rowNode = rowNode[:bottom]
          end
     end
     
     def uncover(r) #when passed a column header, it 'unhides' that column and the rows that could satisfy it
          puts "uncover"
          colNode = r[:colHeader]
          rowNode = colNode[:top]
          until rowNode.equal? colNode
               leftNode = rowNode[:left]
               until leftNode = rowNode
                    leftNode[:top][:bottom] = leftNode
                    leftNode[:bottom][:top] = leftNode
                    leftNode = leftNode[:left]
               end
               rowNode = rowNode[:top]
          end
     end
     
     def find(toFind)
          puts "find"
          rightNode = @root[:right]
          until rightNode.equal? @root #iterate through columns
               #puts "find column - " + i.to_s
               bottomNode = rightNode[:bottom]
               until bottomNode.equal? rightNode #iterate through rows
                    if bottomNode[:row].equal? toFind[:row] and bottomNode[:column].equal? toFind[:column] and bottomNode[:value] = toFind[:value]
                         return bottomNode
                    end
                    bottomNode = bottomNode[:bottom]
               end
               rightNode = rightNode[:right]
          end
          puts "finished find - Not found"
          return nil
     end
     
     def chooseNextColumn()
          puts "chooseNextColumn"
          currentBest = @root[:right]
          best = -1
          tempCount = 0
          nextCol = currentBest
          until nextCol.equal? @root
               nextNode = nextCol[:bottom]

               until nextNode.equal? nextCol
                    #puts "error! Next = Next[:bottom]" if nextNode == nextNode[:bottom]
                    tempCount += 1
                    nextNode = nextNode[:bottom]
               end
               
               if tempCount < best or best == -1
                    currentBest = nextCol
                    best = tempCount
               end
               
               nextCol = nextCol[:right]
          end
          
          if currentBest.equal? @root #Then there is an issue
               puts "Attempted to choose column from empty matrix!"
          end
          
          @count = best
          return currentBest
     end
end

testPuzzle = [2,7,6,0,0,9,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,5,8,2,0,0,6,1,0,0,0,0,0,0,9,0,0,3,0,2,0,8,0,0,4,0,0,0,0,0,0,5,6,0,0,4,1,8,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,9,0,0,6,8,3]
puzzle = SudokuMatrix.new
puzzle.loadPuzzle(testPuzzle)
#puts ObjectSpace.each_object(Node).count
puzzle.solvePuzzle()
puzzle.printSolution()